package tree.迭代bfs;

import java.util.ArrayList;
import java.util.List;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N二叉树寻路1104.java
 * @Description https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/
 * @createTime 2021年08月30日 18:52:00
 */
public class N二叉树寻路1104 {
	public List<Integer> pathInZigZagTree(int label) {

		List<Integer> res = new ArrayList<>();

		// 为了更好的理解解题思路，下面代码不写的太抽象，尽量跟思路中描述的保持一致
		// label 为 1 时，直接返回
		if (label == 1) {
			res.add(1);
			return res;
		}

		// 找到所在层级
		int level = 1;
		int init = 1;
		//每一层的个数为 2^(level-1)  找到数字所在的层数
		while (init << 1 <= label) {
			level++;
			init <<= 1;
		}

		// 构建出尾元素
		res.add(label);

		//按照奇数偶数行，分别取当前行的最后一个 或者第一个
		for (int i = level - 1; i > 1; i--) {
			int cur = label >> 1;
			//i % 2
			res.add(0, i % 2 != level % 2 ? (1 << (i - 1)) + (1 << i) - 1 - cur : cur);
			label = cur;
		}

		// 最后将 1 添加进结果集
		res.add(0, 1);

		return res;

	}
}
